package DataStructure.stack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;

/**
 * 496. 下一个更大元素 I https://leetcode.cn/problems/next-greater-element-i/
 * 题目简述：获取nums1数组中的元素在nums2数组中的下一个更大元素（没有则为-1），nums1是num2的子集且都为不重复数组
 */
public class NextGreaterElement {

    public static void main(String[] args) {
        new NextGreaterElement().nextGreaterElement(new int[]{1,3,5,2,4}, new int[]{6,5,4,3,2,1,7});
    }

    /**
     * 思路：单调栈。从后往前扫描nums2，先将栈中所有小于等于当前元素移除，剩下若栈顶不为空则栈顶元素为当前元素的下一个更大元素，
     * 使用一个map记录。最后将当前元素的索引入栈。最后扫描nums[1]，并从map中获取结果map.getOrDefault(nums1[i], -1)
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();//Map<元素, 元素的下一个更大元素>
        //Deque接口中定义了pop()、push()、peek()方法，因此可以直接当做栈使用
        Deque<Integer> stack = new ArrayDeque<>();//单调栈，存储数据索引
        for (int i = nums2.length-1;i >= 0;i--) {
            while (stack.peek() != null && nums2[stack.peek()] <= nums2[i]) //先移除单调栈中所有小于等于nums2[i]的元素
                stack.pop();
            if (stack.peek() != null) map.put(nums2[i], nums2[stack.peek()]); //此时若栈不为空，则存储nums2[i]下一个更大元素
            stack.push(i); //操作完后将下标入栈
        }
        int[] result = new int[nums1.length];
        for (int i = 0;i < nums1.length;i++) {
            result[i] = map.getOrDefault(nums1[i], -1); //从map中获取结果
        }
        return result;
    }
}
